package com.ddshuai.easy;

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 描述 新通教育
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
 * <p>
 * 示例 1:
 * 输入:
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 输出: [3, 14.5, 11]
 * 解释:
 * 第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
 * <p>
 * 注意：
 * <p>
 * 节点值的范围在32位有符号整数范围内。
 *
 * @author ddshuai
 * @date 2018-09-30 下午2:38
 **/
public class AverageOfLevels {
    public static List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<Double> result = new ArrayList<>();
        queue.add(root);
        int count = 0;
        int num = 0;
        List<TreeNode> list = new ArrayList<>();
        while (!queue.isEmpty() || list.size() > 0) {
            if (queue.isEmpty() && list.size() > 0) {
                result.add(new BigDecimal(count).divide(new BigDecimal(num),5,BigDecimal.ROUND_DOWN).doubleValue());
                count = 0;
                num = 0;
                queue.addAll(list);
                list.clear();
            } else {
                TreeNode treeNode = ((ArrayDeque<TreeNode>) queue).pop();
                count += treeNode.val;
                num++;
                if (treeNode.right != null){
                    list.add(treeNode.right);
                }
                if (treeNode.left != null){
                    list.add(treeNode.left);
                }
            }

        }
        result.add(new BigDecimal(count).divide(new BigDecimal(num),5,BigDecimal.ROUND_DOWN).doubleValue());
        return result;
    }

   static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new AverageOfLevels.TreeNode(1);
        TreeNode treeNode1 = new AverageOfLevels.TreeNode(2);
        TreeNode treeNode2 = new AverageOfLevels.TreeNode(3);
        TreeNode treeNode3 = new AverageOfLevels.TreeNode(4);
        TreeNode treeNode4 = new AverageOfLevels.TreeNode(5);
        TreeNode treeNode5 = new AverageOfLevels.TreeNode(6);
        TreeNode treeNode6 = new AverageOfLevels.TreeNode(7);

        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode2.left = treeNode5;
        treeNode2.right = treeNode6;

        System.out.println(averageOfLevels(treeNode));
    }
}
